package likou;

import java.util.*;

/**
 * @author: Tangxz
 * @email:1171702529@qq.com
 * @cate: 2020/11/05 06:04
 */
//单词接龙
public class _127 {
    public static void main(String[] args) {
        List<String> stringList  = new ArrayList<>();
        stringList.add("hot");
        stringList.add("dot");
        stringList.add("dog");
        stringList.add("lot");
        stringList.add("log");
        stringList.add("cog");
        System.out.println(ladderLength("hit","cog",stringList));
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }
        //hashset的好处：去重也完成了
        //开始端
        HashSet<String> start = new HashSet<>();
        //结束端
        HashSet<String> end = new HashSet<>();
        //所有字符串的字典
        HashSet<String> dic = new HashSet<>(wordList);
        start.add(beginWord);
        end.add(endWord);
        if (!dic.contains(endWord)) {
            return 0;
        }
        //经历过上面的一系列判定，到这里的时候，若是有路径，则最小是2，所以以2开始
        return bfs(start, end, dic, 2);

    }

    public static int bfs(HashSet<String> st, HashSet<String> ed, HashSet<String> dic, int l) {
        //双端查找的时候，若是有任意一段出现了“断裂”，也就是说明不存在能够连上的路径，则直接返回0
        if (st.size() == 0) {
            return 0;
        }
        if (st.size() > ed.size()) {//双端查找，为了优化时间，永远用少的去找多的，比如开始的时候塞进了1000个，而结尾只有3个，则肯定是从少的那一端开始走比较好
            return bfs(ed, st, dic, l);
        }
        //BFS的标记行为，即使用过的不重复使用
        dic.removeAll(st);
        //收集下一层临近点
        HashSet<String> next = new HashSet<>();
        //遍历当前这一层的字符串
        for (String s : st) {
            char[] arr = s.toCharArray();
            //遍历当前层的当前字符串中的每一个字符
            for (int i = 0; i < arr.length; i++) {
                char tmp = arr[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    //如果当前字符相同，则跳过
                    if (tmp == c) {
                        continue;
                    }
                    //如果当前字符不同，则把当前字符替换为现在轮到的字符
                    arr[i] = c;
                    String nstr = new String(arr);
                    //然后去 目标字符串集合中找，是否存在该改变后的字符串
                    if (dic.contains(nstr)) {
                        //如果在结果集合中存在该改变后的字符串，则表示，当前单词接龙中的所有字符串均已出现，就直接返回长度
                        if (ed.contains(nstr)) {
                            return l;
                        } else {
                            //存储下一层的全部字符串。
                            next.add(nstr);
                        }
                    }
                }
                //因为每次只替换一个值，所以每次替换完成一个值并处理完成之后都要复原。
                //复原
                //复原后，继续处理下一个字符，再替换下一个字符，查找是否存在
                arr[i] = tmp;
            }
        }
        //每次递归，都会找到一个单词接龙中的元素，所以每次都直接加一
        return bfs(next, ed, dic, l + 1);
    }
}
